(in-ns 'com.dubious.clojure)

; Euler published the remarkable quadratic formula:
;
; n² + n + 41
;
; It turns out that the formula will produce 40 primes for the consecutive values n = 0 to 39. 
; However, when n = 40, 402 + 40 + 41 = 40(40 + 1) + 41 is divisible by 41, and certainly when 
; n = 41, 41² + 41 + 41 is clearly divisible by 41.
;
; Using computers, the incredible formula  n²  79n + 1601 was discovered, which produces 80 primes
; for the consecutive values n = 0 to 79. The product of the coefficients, 79 and 1601, is 126479.
;
; Considering quadratics of the form:
;
; n² + an + b, where |a| < 1000 and |b| < 1000
; where |n| is the modulus/absolute value of n
; e.g. |11| = 11 and |-4| = 4
;
; Find the product of the coefficients, a and b, for the quadratic expression that produces the 
; maximum number of primes for consecutive values of n, starting with n = 0.

(defn is-prime [value]
  (if (< value 2) 
    ; value is < 2, so it is not even worth checking if it is prime
    0
  
    ; else: loop through possible divisors [2, sqrt(value)]
    (let [upperBound (int (Math/sqrt value))]
      (loop [n 2]
        (if (> n upperBound)
          ; done with the loop, did not find a divisor
          1
          ; else: check the number as possible divisor
          (if (= 0 (mod value n))
            ; found a divisor
            0
            ; else: check the next number
            (recur (inc n))
          )
        )
      )
    )
  )
)

(defn consecutive-primes-using-quadratic [a b]
  (loop [n 0]
    (if (= 1 (is-prime (+ (* n n) (* a n) b)))
      ; f(n) is prime, search for the next
      (recur (inc n))
      ; else: have found all primes, return n
      n
    )
  )
)

(defn consecutive-primes-using-quadratic-loop [a, bounds]
  ; this loop controls the second coefficient, b
  (loop [b (- bounds),
         maxResultB 0,
         productForResultB 0]
    (if (<= b bounds)
      (let [result (consecutive-primes-using-quadratic a b)]
        (if (> result maxResultB)
          ; found a better result
          (do
            ; (println "found result at level B. a:" a ", b:" b ", n:" result)
            (recur (inc b), result, (* a b))
          )
          ; did not find a better result
          (recur (inc b), maxResultB, productForResultB)
        )
      )
      ; else: have result, return it
      [maxResultB, productForResultB]
    )
  )
)


(defn find-coefficients [bounds]
  ; loop through all combinations of [-bounds, bounds]x[-bounds, bounds]
  (loop [a (- bounds),
         maxResultA 0,
         productForResultA 0]
    ; this loop controls the first coefficient, a
    (if (<= a bounds)
      (let [result (consecutive-primes-using-quadratic-loop a bounds)]
        (if (> (first result) maxResultA)
          ; found a better result
          (do
            (println "found result at level A. a:" a ", b:" (/ (second result) a) ", n:" (first result))
            (recur (inc a), (first result), (second result))
          )
          ; did not find a better result
          (recur (inc a), maxResultA, productForResultA)
        )
      )
      ; else: have result, return the product
      productForResultA
    )
  )
)

(defn problem-27 [bounds]
  (println "Product of the coefficients: " (find-coefficients bounds))
)
